{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Sudoku"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValidSudoku"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的数独"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请你判断一个&nbsp;<code>9 x 9</code> 的数独是否有效。只需要<strong> 根据以下规则</strong> ，验证已经填入的数字是否有效即可。</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>数字&nbsp;<code>1-9</code>&nbsp;在每一行只能出现一次。</li>\n",
    "\t<li>数字&nbsp;<code>1-9</code>&nbsp;在每一列只能出现一次。</li>\n",
    "\t<li>数字&nbsp;<code>1-9</code>&nbsp;在每一个以粗实线分隔的&nbsp;<code>3x3</code>&nbsp;宫内只能出现一次。（请参考示例图）</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个有效的数独（部分已被填充）不一定是可解的。</li>\n",
    "\t<li>只需要根据以上规则，验证已经填入的数字是否有效即可。</li>\n",
    "\t<li>空白格用&nbsp;<code>'.'</code>&nbsp;表示。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714svg.png\" style=\"height:250px; width:250px\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = \n",
    "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = \n",
    "[[\"8\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>除了第一行的第一个数字从<strong> 5</strong> 改为 <strong>8 </strong>以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>board.length == 9</code></li>\n",
    "\t<li><code>board[i].length == 9</code></li>\n",
    "\t<li><code>board[i][j]</code> 是一位数字（<code>1-9</code>）或者 <code>'.'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-sudoku](https://leetcode.cn/problems/valid-sudoku/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-sudoku](https://leetcode.cn/problems/valid-sudoku/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]', '[[\"8\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        appearance = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] != \".\":\n",
    "                    if board[i][j] not in appearance:\n",
    "                        appearance[board[i][j]] = {'col':[], 'row':[], 'sub_index':[]}\n",
    "                    if i in appearance[board[i][j]]['col']:\n",
    "                        return False\n",
    "                    else:\n",
    "                        appearance[board[i][j]]['col'].append(i)\n",
    "                    if j in appearance[board[i][j]]['row']:\n",
    "                        return False\n",
    "                    else:\n",
    "                        appearance[board[i][j]]['row'].append(j)\n",
    "                    sub_index = i//3+(j//3)*3\n",
    "                    if sub_index in appearance[board[i][j]]['sub_index']:\n",
    "                        return False\n",
    "                    else:\n",
    "                        appearance[board[i][j]]['sub_index'].append(sub_index)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dic_row = [{},{},{},{},{},{},{},{},{}]  # 每行的元素以一个字典储存，key是数字，value统一为1.\n",
    "        dic_col = [{},{},{},{},{},{},{},{},{}]\n",
    "        dic_box = [{},{},{},{},{},{},{},{},{}]\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board)):\n",
    "                num = board[i][j]\n",
    "                if num == \".\":\n",
    "                     continue\n",
    "                if num not in dic_row[i] and num not in dic_col[j] and num not in dic_box[3*(i//3)+(j//3)]:\n",
    "                    dic_row[i][num] = 1\n",
    "                    dic_col[j][num] = 1\n",
    "                    dic_box[3*(i//3)+(j//3)][num] = 1  # 利用地板除，向下取余。巧妙地将矩阵划分为九块\n",
    "                else:\n",
    "                    return False\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def check(arr):\n",
    "            used = [False] * 9\n",
    "            for c in arr:\n",
    "                if c != '.':\n",
    "                    i = ord(c) - ord('1')\n",
    "                    if used[i]:\n",
    "                        return False\n",
    "                    used[i] = True\n",
    "            return True\n",
    "        \n",
    "        for r in board:\n",
    "            if not check(r):\n",
    "                return False\n",
    "        for j in range(9):\n",
    "            arr = []\n",
    "            for i in range(9):\n",
    "                arr.append(board[i][j])\n",
    "            if not check(arr):\n",
    "                return False\n",
    "        for a in [0, 1, 2]:\n",
    "            for b in [0, 1, 2]:\n",
    "                arr = []\n",
    "                for c in [0, 1, 2]:\n",
    "                    for d in [0, 1, 2]:\n",
    "                        arr.append(board[a * 3 + c][b * 3 + d])\n",
    "                if not check(arr):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: 'List[List[str]]') -> 'bool':\n",
    "        for i in range(9):\n",
    "            temp = board[i].copy()\n",
    "            temp = [item for item in temp if item != '.']\n",
    "            print(temp, set(temp))\n",
    "            if len(temp) != len(set(temp)):\n",
    "                # print('1')\n",
    "                return False\n",
    "        for j in range(9):\n",
    "            temp = [item[j] for item in board if item[j] != '.']\n",
    "            if len(temp) != len(set(temp)):\n",
    "                # print('2')\n",
    "                return False\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                temp = [board[m][n] for m in range(i*3,(i+1)*3) for n in range(j*3, (j+1)*3) if board[m][n] != '.']\n",
    "                if len(temp) != len(set(temp)):\n",
    "                    # print('3')\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import product\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        groups = []\n",
    "        groups += [list((i, j) for i in range(9)) for j in range(9)]\n",
    "        groups += [list((j, i) for i in range(9)) for j in range(9)]\n",
    "        groups += [list(product(range(x*3, x*3+3), range(y*3, y*3+3)))\n",
    "                   for x, y in product(range(3), range(3))]\n",
    "        \n",
    "        for g in groups:\n",
    "            ns = set()\n",
    "            for r, c in g:\n",
    "                n = board[r][c]\n",
    "                if n == '.':\n",
    "                    continue\n",
    "                if n in ns:\n",
    "                    return False\n",
    "                ns.add(n)\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        raw = [{},{},{},{},{},{},{},{},{}]\n",
    "        col = [{},{},{},{},{},{},{},{},{}]\n",
    "        cell = [{},{},{},{},{},{},{},{},{}]\n",
    "        \n",
    "        for i in range(9):\n",
    "            for j in range(9):                                 \n",
    "                num = (3*(i//3) + j//3)#找单元\n",
    "                temp = board[i][j]\n",
    "                if temp != \".\":\n",
    "                    if temp not in raw[i] and temp not in col[j] and temp not in cell[num]:\n",
    "                        raw [i][temp] = 1\n",
    "                        col [j][temp] = 1\n",
    "                        cell [num][temp] =1\n",
    "                    else:\n",
    "                        return False    \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        for x in range(9):\n",
    "            for y in range(9):\n",
    "                if board[x][y] != '.':\n",
    "                    m,n = (x//3)*3,(y//3)*3\n",
    "                    for i in range(9):\n",
    "                        if y != i and board[x][i] == board[x][y]:\n",
    "                            return False\n",
    "                    for i in range(9):\n",
    "                        if x != i and board[i][y] == board[x][y]:\n",
    "                            return False\n",
    "                    for i in range(3):\n",
    "                        for j in range(3):\n",
    "                            if ((m+i)!=x or (n+j)!=y) and board[m+i][n+j] == board[x][y]:\n",
    "                                return False\n",
    "        return True\n",
    "                    \n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for i in range(9):\n",
    "            if not self.isValidNine(board[i]):\n",
    "                return False\n",
    "            col = [c[i] for c in board]\n",
    "            if not self.isValidNine(col):\n",
    "                return False\n",
    "        for i in [0, 3, 6]:\n",
    "            for j in [0, 3, 6]:\n",
    "                block = [board[s][t] for s in [i, i+1, i+2] for t in [j, j+1, j+2]]\n",
    "                if not self.isValidNine(block):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def isValidNine(self, row):\n",
    "        map = {}\n",
    "        for c in row:\n",
    "            if c != '.':\n",
    "                if c in map:\n",
    "                    return False\n",
    "                else:\n",
    "                    map[c] = True\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "    \tflag_l=0\n",
    "    \tfor i in range(0,9):\n",
    "\n",
    "\t    \tseem_row=set()\n",
    "\t    \tseem_col=set()\n",
    "\t    \tflag=0\n",
    "    \t\tfor j in range(0,9):\n",
    "    \t\t\tif(board[i][j]!=\".\"):\n",
    "\t    \t\t\tif(board[i][j] not in seem_row):\n",
    "\t    \t\t\t\tseem_row.add(board[i][j])\n",
    "\t    \t\t\telse:\n",
    "\t    \t\t\t\treturn False\n",
    "\t    \t\tif(board[j][i]!=\".\"):\n",
    "\t    \t\t\tif(board[j][i] not in seem_col):\n",
    "\t    \t\t\t\tseem_col.add(board[j][i])\n",
    "\t    \t\t\telse:\n",
    "\t    \t\t\t\treturn False\n",
    "\n",
    "\n",
    "    \tfor j in range(1,10):\n",
    "\t    \tseem_block=set()\n",
    "\t    \tprint()\n",
    "\t    \tflag_l+=1\n",
    "\t    \tif(j<=3):\n",
    "\t    \t\tflag=0\n",
    "\t    \telif(j<=6):\n",
    "\t    \t\tflag=3\n",
    "\t    \telse:\n",
    "\t    \t\tflag=6\n",
    "\t    \tfor k in range(flag,flag+3):\n",
    "\n",
    "\t    \t\tif(flag_l==4):\n",
    "\t    \t\t\tflag_l=1\n",
    "\t    \t\tfor l in range((flag_l-1)*3,flag_l*3):\n",
    "\t    \t\t\tif(board[k][l]!=\".\"):\n",
    "\t    \t\t\t\tprint(k,l)\n",
    "\t    \t\t\t\tif(board[k][l] not in seem_block):\n",
    "\t    \t\t\t\t\tseem_block.add(board[k][l])\n",
    "\t    \t\t\t\telse:\n",
    "\t\t    \t\t\t\treturn False\n",
    "    \treturn True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        for z in range(9):\n",
    "            #判断第i行i列的有效性\n",
    "            rowList = []\n",
    "            colList = []\n",
    "            for i in range(9):\n",
    "                if board[z][i] != '.' and board[z][i] in rowList:\n",
    "                    return False\n",
    "                else:\n",
    "                    rowList.append(board[z][i])\n",
    "                if board[i][z] != '.' and board[i][z] in colList:\n",
    "                    return False\n",
    "                else:\n",
    "                    colList.append(board[i][z])\n",
    "            i = 3*(z // 3)\n",
    "            j = 3*(z % 3)\n",
    "            boxList = []\n",
    "            print(i, j)\n",
    "            for ii in range(i, i+3):\n",
    "                for jj in range(j,j+3):\n",
    "                    #print(ii,jj)\n",
    "                    if board[ii][jj] != '.' and board[ii][jj] in boxList:\n",
    "                        return False\n",
    "                    else:\n",
    "                        boxList.append(board[ii][jj])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        len_b = len(board)\n",
    "        for i in range(len_b):\n",
    "            set_row = set()\n",
    "            set_col = set()\n",
    "            for j in range(len_b):\n",
    "                if \"1\" <= board[i][j] <= \"9\":\n",
    "                    if board[i][j] in set_row:\n",
    "                        return False\n",
    "                    else:\n",
    "                        set_row.add(board[i][j])\n",
    "                if \"1\" <= board[j][i] <= \"9\":\n",
    "                    if board[j][i] in set_col:\n",
    "                        return False\n",
    "                    else:\n",
    "                        set_col.add(board[j][i])\n",
    "        for k in range(2,9,3):\n",
    "            for h in range(2,9,3):\n",
    "                set_cube = set()\n",
    "                for i in range(h-2,h+1):\n",
    "                    for j in range(k-2,k+1):\n",
    "                        if \"1\" <= board[i][j] <= \"9\":\n",
    "                            if board[i][j] in set_cube:\n",
    "                                return False\n",
    "                            else:\n",
    "                                set_cube.add(board[i][j])\n",
    "        return True\n",
    "                        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def validate(l):\n",
    "            tmp = [ch for ch in l if ch != '.']\n",
    "            return len(set(tmp)) == len(tmp)\n",
    "        # validate row\n",
    "        for row in board:\n",
    "            if not validate(row):\n",
    "                return False\n",
    "        # validate colomn\n",
    "        for i in range(9):\n",
    "            if not validate([board[j][i] for j in range(9)]):\n",
    "                return False\n",
    "        # validate 3 x 3\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if not validate([board[3 * i + p][3 * j + q] for p in range(3) for q in range(3)]):\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def isValid(x, y, temp):\n",
    "            for i in range(9):\n",
    "                if board[i][y] == temp:\n",
    "                    return False\n",
    "            for j in range(9):\n",
    "                if board[x][j] == temp:\n",
    "                    return False\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if board[(x//3)*3+i][(y//3)*3+j] == temp:\n",
    "                        return False\n",
    "            return True\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == '.':\n",
    "                    continue\n",
    "                temp = board[i][j]\n",
    "                board[i][j] = 'D'\n",
    "                if isValid(i, j, temp) == False:\n",
    "                    return False\n",
    "                else:\n",
    "                    board[i][j] == temp\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        for i in range(len(board)):\n",
    "            list1 = []\n",
    "            for j in range(len(board[i])):\n",
    "                if board[i][j] == \".\":\n",
    "                    continue\n",
    "                else:\n",
    "                    if board[i][j] in list1:\n",
    "                        return False\n",
    "                    else:\n",
    "                        list1.append(board[i][j])\n",
    "        for i2 in range(len(board[0])):\n",
    "            list2 = []\n",
    "            for j2 in range(len(board)):\n",
    "                if board[j2][i2] == \".\":\n",
    "                    continue\n",
    "                else:\n",
    "                    if board[j2][i2] in list2:\n",
    "                        return False\n",
    "                    else:\n",
    "                        list2.append(board[j2][i2])\n",
    "        for i3 in range(0,3):\n",
    "            for k3 in range(0,3):\n",
    "                list3 = []\n",
    "                for j3 in range(i3*3,(i3+1)*3):\n",
    "                    for q3 in range(k3*3,(k3+1)*3):\n",
    "                        if board[j3][q3] == \".\":\n",
    "                            continue\n",
    "                        else:\n",
    "                            if board[j3][q3] in list3:\n",
    "                                return False\n",
    "                            else:\n",
    "                                list3.append(board[j3][q3])\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        seen = []\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                for c in [board[i][j]]:\n",
    "                    if c != '.':\n",
    "                        seen += (c,i), (j,c), (i//3, j//3, c)\n",
    "        return len(seen) == len(set(seen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        rows=[[0]*10 for x in range(9)]\n",
    "        cols=[[0]*10 for x in range(9)]\n",
    "        sons=[[0]*10 for x in range(9)]\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j]!='.':\n",
    "                    val=int(board[i][j])\n",
    "                    rows[i][val]+=1\n",
    "                    cols[j][val]+=1\n",
    "                    sonID=(i//3)*3+j//3\n",
    "                    sons[sonID][val]+=1\n",
    "                    if rows[i][val]>1 or cols[j][val]>1 or sons[sonID][val]>1:\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        r = [[] for _ in range(9)]\n",
    "        c = [[] for _ in range(9)]\n",
    "        b = [[] for _ in range(9)]\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                cur = board[i][j]\n",
    "                if cur != '.':\n",
    "                    if cur not in r[i]:\n",
    "                        r[i].append(cur)\n",
    "                    else:\n",
    "                        return False\n",
    "                    if cur not in c[j]:\n",
    "                        c[j].append(cur)\n",
    "                    else:\n",
    "                        return False\n",
    "                    block = i//3 * 3 + j//3\n",
    "                    if cur not in b[block]:\n",
    "                        b[block].append(cur)\n",
    "                    else:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        hang_dic = {}\n",
    "        lie_dic = {}\n",
    "        gong_dic = {}\n",
    "               \n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] != \".\":\n",
    "                    if board[i][j] in hang_dic:\n",
    "                        return False\n",
    "                    else:\n",
    "                        hang_dic[board[i][j]] = 1\n",
    "            hang_dic = {}\n",
    "            \n",
    "        for j in range(len(board[0])):\n",
    "            for i in range(len(board)):\n",
    "                if board[i][j] != \".\":\n",
    "                    if board[i][j] in lie_dic:\n",
    "                        return False\n",
    "                    else:\n",
    "                        lie_dic[board[i][j]] = 1\n",
    "            lie_dic = {}\n",
    "            \n",
    "        def isgong(i, j, gong_dic):\n",
    "            for p in range(3):\n",
    "                for q in range(3):\n",
    "                    if board[i + p][j + q] != \".\":\n",
    "                        if board[i + p][j + q] in gong_dic:\n",
    "                            return False\n",
    "                        else:\n",
    "                            gong_dic[board[i + p][j + q]] = 1\n",
    "            return True\n",
    "        res = True\n",
    "        for i in range(0, 9, 3):\n",
    "            for j in range(0, 9, 3):\n",
    "                res = isgong(i, j, {})\n",
    "                if not res:\n",
    "                    return False\n",
    "        return res\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        cnt_row = [collections.Counter() for _ in range(9)]\n",
    "        cnt_col = [collections.Counter() for _ in range(9)]\n",
    "        cnt_grid = [[collections.Counter() for _ in range(3)] for _ in range(3)]\n",
    "        \n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    cnt_grid[i // 3][j // 3][board[i][j]] += 1\n",
    "                    cnt_row[i][board[i][j]] += 1\n",
    "                    cnt_col[j][board[i][j]] += 1\n",
    "\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k, v in cnt_grid[i][j].items():\n",
    "                    if v > 1:\n",
    "                        return False\n",
    "        print(cnt_col[3].items())\n",
    "        for i in range(9):\n",
    "            for k, v in cnt_col[i].items():\n",
    "                if v > 1:\n",
    "                    return False\n",
    "            for k, v in cnt_row[i].items():\n",
    "                if v > 1:\n",
    "                    return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        for i in range(9):\n",
    "            temp = []\n",
    "            for j in range(9):\n",
    "                if board[i][j].isdigit() and board[i][j] in temp :\n",
    "                    return False\n",
    "                else:\n",
    "                    temp.append(board[i][j])\n",
    "    # 列\n",
    "        for i in range(9):\n",
    "            temp = []\n",
    "            for j in range(9):\n",
    "                if board[j][i].isdigit() and board[j][i] in temp :\n",
    "                    return False\n",
    "                else:\n",
    "                    temp.append(board[j][i])\n",
    "    # 小区域\n",
    "        n = 0\n",
    "        a = 3\n",
    "        while a <= 9:\n",
    "            m = 0\n",
    "            b = 3\n",
    "            while b <= 9:\n",
    "                temp = []\n",
    "                for i in range(n,a):\n",
    "                    for j  in range(m,b):\n",
    "                        if board[i][j].isdigit() and board[i][j] in temp:\n",
    "                            return False\n",
    "                        else:\n",
    "                            temp.append(board[i][j])\n",
    "                m += 3\n",
    "                b += 3\n",
    "            n += 3\n",
    "            a += 3\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        def isvalid(ls:List)->bool:\n",
    "            d=dict()\n",
    "            for x in ls:\n",
    "                if x!='.' and x in d:\n",
    "                    return False\n",
    "                if x!='.' and x not in d:\n",
    "                    d[x]=1\n",
    "            return True\n",
    "\n",
    "        #行\n",
    "        for x in board:\n",
    "            if not isvalid(x):\n",
    "                return False\n",
    "        \n",
    "        #列\n",
    "\n",
    "        for i in range(9):\n",
    "            ls=[]\n",
    "            for j in range(9):\n",
    "                ls.append(board[j][i])\n",
    "            if not isvalid(ls):\n",
    "                return False\n",
    "        \n",
    "        for i in range(0,9,3):\n",
    "            for j in range(0,9,3):\n",
    "                ls=[]\n",
    "                for k in range(0,3):\n",
    "                    for l in range(0,3):\n",
    "                        ls.append(board[i+k][j+l])\n",
    "                if not isvalid(ls):\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        n = 9\n",
    "        # init data\n",
    "        rows = [{} for i in range(n)]\n",
    "        columns = [{} for i in range(n)]\n",
    "        boxes = [{} for i in range(n)]\n",
    "\n",
    "        # validate a board\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                num = board[i][j]\n",
    "                if num != '.':\n",
    "                    num = int(num)\n",
    "                    # 第几个盒子\n",
    "                    box_index = (i // 3 ) * 3 + j // 3\n",
    "                    # 记录下来\n",
    "                    rows[i][num] = rows[i].get(num, 0) + 1\n",
    "                    columns[j][num] = columns[j].get(num, 0) + 1\n",
    "                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1\n",
    "                    # check if this value has been already seen before\n",
    "                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "\n",
    "        rows = len(board)\n",
    "        cols = len(board[0])\n",
    "\n",
    "        rows_exist = [False] * cols\n",
    "        cols_exist = [[False] * 9 for i in range(cols)]\n",
    "        \n",
    "        grid_exist = [[False] * 9 for i in range(3)]\n",
    "\n",
    "        for i in range(rows):\n",
    "            rows_exist = [False] * cols\n",
    "            if i % 3 == 0:\n",
    "                grid_exist = [[False] * 9 for k in range(3)]\n",
    "            for j in range(cols):\n",
    "\n",
    "                grid_index = ((i//3) * 3 + j // 3)%3\n",
    "                if board[i][j] == '.':\n",
    "                    continue\n",
    "                num = int(board[i][j])\n",
    "                print(grid_index, num, i, j)\n",
    "                if rows_exist[num-1] or cols_exist[j][num-1] or grid_exist[grid_index][num-1]:\n",
    "                    print(rows_exist[num-1],cols_exist[j][num-1] ,grid_exist[grid_index][num-1])\n",
    "                    return False\n",
    "                else:\n",
    "                    rows_exist[num-1] = True\n",
    "                    cols_exist[j][num-1] = True\n",
    "                    grid_exist[grid_index][num-1] = True\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        for i in range(9):\n",
    "            flag_row,flag_col,flag_grid=0,0,0\n",
    "            for j in range(9):\n",
    "                flag_row=self.judge(flag_row,board[i][j])\n",
    "                flag_col=self.judge(flag_col,board[j][i])\n",
    "                flag_grid=self.judge(flag_grid,board[j//3+(i//3)*3][j%3+(i%3)*3])\n",
    "                print(flag_row)\n",
    "                print(flag_col)\n",
    "                print(flag_grid)\n",
    "                if flag_row==-1 or flag_col==-1 or flag_grid==-1:\n",
    "                    return False\n",
    "                #print(bin(flag_col))\n",
    "        return True\n",
    "\n",
    "\n",
    "    \n",
    "    def judge(self,flag,val):\n",
    "        if val=='.': return flag\n",
    "        val=int(val)-1\n",
    "        if (flag>>val)&1==1:\n",
    "            return -1\n",
    "        else:\n",
    "            flag=(1<<val)+flag\n",
    "            return flag\n",
    "'''\n",
    "[[\"8\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],\n",
    "[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],\n",
    "[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],\n",
    "[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],\n",
    "[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],\n",
    "[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],\n",
    "[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],\n",
    "[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],\n",
    "[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board) -> bool:\n",
    "        for i in range(9):\n",
    "            unique = []\n",
    "            for j in range(9):\n",
    "                if (board[i][j] not in unique) or (board[i][j]==\".\") :\n",
    "                    unique.append(board[i][j])\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        for i in range(9):\n",
    "            unique = []\n",
    "            for j in range(9):\n",
    "                if (board[j][i] not in unique) or (board[j][i]==\".\"):\n",
    "                    unique.append(board[j][i])\n",
    "                else:\n",
    "                    return False\n",
    "        row = 0\n",
    "        columns = 0\n",
    "        while row<=6:\n",
    "            while columns <=6:\n",
    "                unique = []\n",
    "                for i in range(3):\n",
    "\n",
    "                    for j in range(3):\n",
    "                        if (board[row+i][columns+j] not in unique) or (board[row+i][columns+j]==\".\"):\n",
    "                            unique.append(board[row+i][columns+j])\n",
    "                        else:\n",
    "                            return False\n",
    "                        print(row+i,columns+j)\n",
    "                columns+=3\n",
    "            row+=3\n",
    "            columns=0\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "        row = [[] * 9 for _ in range(9)]\n",
    "        col = [[] * 9 for _ in range(9)]\n",
    "        nine = [[] * 9 for _ in range(9)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                tmp = board[i][j]\n",
    "                if not tmp.isdigit():\n",
    "                    continue\n",
    "                if tmp in row[i]:\n",
    "                    return False\n",
    "                if tmp in col[j]:\n",
    "                    return False\n",
    "                if tmp in nine[(j // 3) * 3 + (i // 3)]:\n",
    "                    return False\n",
    "                row[i].append(tmp)\n",
    "                col[j].append(tmp)\n",
    "                nine[(j // 3) * 3 + (i // 3)].append(tmp)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        rows = {}\n",
    "        cols = {}\n",
    "        boxes = {}\n",
    "        # 遍历数独\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                num = board[i][j]\n",
    "                if num != '.':\n",
    "                    box_index = (i // 3) * 3 + j // 3\n",
    "                    # 检查行、列、块是否出现重复数字\n",
    "                    if (i, num) in rows or (j, num) in cols or (box_index, num) in boxes:\n",
    "                        return False\n",
    "                    else:\n",
    "                        rows[(i, num)] = True\n",
    "\n",
    "                        cols[(j, num)] = True\n",
    "                        boxes[(box_index, num)] = True\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        row = [[] for i in range(9)]\n",
    "        col = [[] for i in range(9)]\n",
    "        box = [[] for i in range(9)]\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                v = board[i][j]\n",
    "                if v!='.':\n",
    "                    if v in row[i] or v in col[j] or v in box[3*(i//3)+j//3]: \n",
    "                        return False\n",
    "                    else:\n",
    "                        row[i].append(v)\n",
    "                        col[j].append(v)\n",
    "                        box[3*(i//3)+j//3].append(v)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        for i in range(9):\n",
    "            tmp = {}\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    if board[i][j] in tmp:\n",
    "                        print(board[i])\n",
    "                        return False\n",
    "                    else: tmp[board[i][j]] = 0\n",
    "        for j in range(9):\n",
    "            tmp = {}\n",
    "            for i in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    if board[i][j] in tmp:\n",
    "                        for m in range(9):\n",
    "                            print(board[m][j])\n",
    "                        return False\n",
    "                    else: tmp[board[i][j]] = 0\n",
    "        for i in range(0, 27, 3):\n",
    "            tmp = {}\n",
    "            for k in range(i % 9,i % 9 + 3):\n",
    "                for j in range(i // 9 * 3, i // 9 * 3 + 3):\n",
    "                    if board[k][j] != '.':\n",
    "                        if board[k][j] in tmp:\n",
    "                            return False\n",
    "                        else: tmp[board[k][j]] = 0\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "\n",
    "        # 解法1  358 / 507\n",
    "        set1 = set()\n",
    "        lst1 = []\n",
    "\n",
    "        # 判断行和列是否有重复数字\n",
    "        for i in range(9):\n",
    "            c1 = board[i].count('.')\n",
    "            # 358 / 507\n",
    "            # 判断行\n",
    "            for j in range(9):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "            # if len(set1) != 9 - c1: return False\n",
    "            if len(set1) != len(lst1): return False\n",
    "\n",
    "            set1.clear()\n",
    "            lst1.clear()\n",
    "            \n",
    "            # 473 / 507\n",
    "            # 判断列\n",
    "            for j2 in range(9):\n",
    "                if board[j2][i] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[j2][i])\n",
    "                    lst1.append(board[j2][i])\n",
    "            if len(set1) != len(lst1): return False\n",
    "\n",
    "            set1.clear()\n",
    "            lst1.clear()\n",
    "\n",
    "        # 判断方格是否有重复数字\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(3):\n",
    "            for j in range(3,6):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(3):\n",
    "            for j in range(6,9):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "        \n",
    "        for i in range(3,6):\n",
    "            for j in range(3):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(3,6):\n",
    "            for j in range(3,6):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(3,6):\n",
    "            for j in range(6,9):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(6,9):\n",
    "            for j in range(3):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(6,9):\n",
    "            for j in range(3,6):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        for i in range(6,9):\n",
    "            for j in range(6,9):\n",
    "                if board[i][j] in ['1', '2', '3' ,'4', '5', '6', '7', '8', '9']:\n",
    "                    set1.add(board[i][j])\n",
    "                    lst1.append(board[i][j])\n",
    "        if len(set1) != len(lst1): return False\n",
    "        set1.clear()\n",
    "        lst1.clear()\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board) -> bool:\n",
    "        a = []\n",
    "        for i in range(9):\n",
    "            a.append([])\n",
    "        x = 0\n",
    "        y = 0\n",
    "        for x in range(len(board)):\n",
    "            for y in range(len(board[x])):\n",
    "                if board[x][y] != \".\":\n",
    "                    a[int(board[x][y])-1].append((x, y))\n",
    "                    print(int(board[x][y]), x, y)\n",
    "        \n",
    "        for i in a:\n",
    "            for left in range(len(i)):\n",
    "                for right in range(left+1, len(i)):\n",
    "                    if i[left][0] == i[right][0] or i[left][1] == i[right][1]:\n",
    "                        return False\n",
    "                    if i[left][0] // 3 == i[right][0] // 3 and i[left][1] // 3 == i[right][1] // 3:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "#         for i in range(9):\n",
    "#             storage = []\n",
    "#             for j in range(9):\n",
    "#                 if board[i][j] == \".\":\n",
    "#                     continue\n",
    "#                 # if board[i][j] in storage:\n",
    "#                 #     return False\n",
    "#                 else:\n",
    "#                     storage.append(board[i][j])\n",
    "#                     if len(storage) != len(set(storage)):\n",
    "#                         return False\n",
    "#         for j in range(9):\n",
    "#             storage = []\n",
    "#             for i in range(9):\n",
    "#                 if board[i][j] == \".\":\n",
    "#                     continue\n",
    "#                 #if board[i][j] in storage:\n",
    "#                     #return False\n",
    "#                 else:\n",
    "#                     storage.append(board[i][j])\n",
    "#                     if len(storage) != len(set(storage)):\n",
    "#                         return False\n",
    "                          \n",
    "#         for i in range(0,9,3):\n",
    "#             for j in range(0,9,3):\n",
    "#                 storage = []\n",
    "#                 for x in range(3):\n",
    "#                     for y in range(3):\n",
    "#                         if board[i+x][j+y] == \".\":\n",
    "#                             continue\n",
    "#                         # if board[i+x][j+y] in storage:\n",
    "#                         #     return False\n",
    "#                         else:\n",
    "#                             storage.append(board[i+x][j+y])\n",
    "#                             if len(storage) != len(set(storage)):\n",
    "#                                 return False\n",
    "#         return True\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "\n",
    "        row = [[0] * 9 for _ in range(9)]\n",
    "        col = [[0] * 9 for _ in range(9)]\n",
    "        block = [[0] * 9 for _ in range(9)]#9个block，一个里面9个数字，第一块放在第一行\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    num = int(board[i][j]) - 1\n",
    "                    b = (i // 3) * 3 + j // 3\n",
    "                    if row[i][num] or col[j][num] or block[b][num]:\n",
    "                        return False\n",
    "                    row[i][num] = col[j][num] = block[b][num] = 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        rows = [{} for _ in range(9)]\n",
    "        cols = [{} for _ in range(9)]\n",
    "        boxs = [{} for _ in range(9)]\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    num = int(board[i][j])\n",
    "                    box_index = j//3%3 + i//3%3*3\n",
    "                    if num in rows[i] or num in cols[j] or num in boxs[box_index]:\n",
    "                        return False\n",
    "                    rows[i][num] = rows[i].get(num,0) + 1\n",
    "                    cols[j][num] = cols[j].get(num,0) + 1\n",
    "                    boxs[box_index][num] = boxs[box_index].get(num,0) + 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSudoku(self, board: List[List[str]]) -> bool:\n",
    "        row = [[0] * 9 for _ in range(9)]\n",
    "        col = [[0] * 9 for _ in range(9)]\n",
    "        block = [[0] * 9 for _ in range(9)]\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    num = int(board[i][j]) - 1\n",
    "                    b = (i // 3) * 3 + j // 3\n",
    "                    if row[i][num] or col[j][num] or block[b][num]:\n",
    "                        return False\n",
    "                    row[i][num] = col[j][num] = block[b][num] = 1\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
